package com.剑指offer.第二章;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

public class 排序数组中的两个数字之和 {

    // hash表解法
    public static int[] resolve(int[] nums, int target) {
        Map<Integer, Integer> maps = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int k = target - nums[i];
            if (maps.containsKey(k)) {
                return new int[]{maps.get(k), i};
            } else {
                maps.put(nums[i], i);
            }
        }
        return new int[]{};
    }

    // 二分查找法
    public static int[] resolve1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int k = target - nums[i];
            int x = 0;
            int j = nums.length - 1;
            while (x <= j) {
                int mid = (x + j) / 2;
                if (nums[mid] < k) {
                    x = mid + 1;
                } else if (nums[mid] > k) {
                    j = mid - 1;
                } else {
                    return new int[]{i, mid};
                }
            }
        }
        return new int[]{};
    }

    // 双指针解法
    public static int[] resolve2(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j && nums[i] + nums[j] != target) {
            if (nums[i] + nums[j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return new int[]{i, j};
    }

    public static void main(String[] args) {
        for (int i : resolve2(new int[]{1, 2, 3, 4, 10, 11}, 5)) {
            System.out.println(i);
        }
    }

}
